package a10_动态规划;

/**
 * <p>
 * a08_整数拆分
 * </p>
 *
 * @author flyduck
 * @since 2025/2/9
 */
public class a08_整数拆分 {
    //dp[i]的含义：对i进行拆分后的最大乘积
    //i拆分成两个数：dp[i] = j * i-j
    //i拆分成多个数：dp[i] = j * dp[i-j]
    //i拆分成多个数会漏吗？假设拆6
    //1 * dp[5]
    //2 * dp[4]这个会不会漏了把2拆分成1*1的情况 1 * 1 * 1 * 1 * 1 * 1，虽然这里会漏，但是上面的1 * dp[5]包含

    //初始化：
    // dp[0]：没有意义 0
    // dp[1]：没有意义 0
    // dp[2]=1

    //遍历顺序：从3开始遍历


    public int integerBreak(int n) {
        int[] dp = new int[n+1];
        dp[0] = 0;
        dp[1] = 0;
        dp[2] = 1;

        for (int i = 3; i <= n; i++) {
            for (int j = 1; j < i; j++) {
                dp[i] = Math.max(Math.max(j * (i-j),j * dp[i-j]), dp[i]);
            }
        }
        return dp[n];
    }
}
